/*
 * Copyright (c) 2002 Shaven Puppy Ltd All rights reserved. Redistribution and use in source and
 * binary forms, with or without modification, are permitted provided that the following conditions
 * are met: * Redistributions of source code must retain the above copyright notice, this list of
 * conditions and the following disclaimer. * Redistributions in binary form must reproduce the
 * above copyright notice, this list of conditions and the following disclaimer in the documentation
 * and/or other materials provided with the distribution. * Neither the name of 'Shaven Puppy' nor
 * the names of its contributors may be used to endorse or promote products derived from this
 * software without specific prior written permission. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT
 * HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
package engine.fov;

/**
 * Bresenham's famous line drawing algorithm. Works for 2D.
 */
final class BresenhamLine {

	/** General case algorithm */
	private static final BresenhamLine bresenham = new BresenhamLine();

	/**
	 * Plot a line between (x1,y1) and (x2,y2). The results are placed in x[] and y[], which must be
	 * large enough.
	 * 
	 * @return the length of the line or the length of x[]/y[], whichever is smaller
	 */
	static final int plot(final int x1, final int y1, final int x2, final int y2, final int x[],
			final int y[]) {

		final int length = Math.min(x.length, Math.min(y.length, BresenhamLine.bresenham.plot(x1,
				y1, x2, y2)));
		for (int i = 0; i < length; i++) {
			x[i] = BresenhamLine.bresenham.getX();
			y[i] = BresenhamLine.bresenham.getY();
			BresenhamLine.bresenham.next();
		}

		return length;
	}

	/** Used for calculation */
	private int dx, dy, error, x_inc, y_inc, xx, yy, length, count;

	/**
	 * Construct a Bresenham algorithm.
	 */
	BresenhamLine() {}

	/**
	 * @return the current X coordinate
	 */
	int getX() {
		return xx;
	}

	/**
	 * @return the current Y coordinate
	 */
	int getY() {
		return yy;
	}

	/**
	 * Get the next point in the line. You must not call next() if the previous invocation of next()
	 * returned false. Retrieve the X and Y coordinates of the line with getX() and getY().
	 * 
	 * @return true if there is another point to come.
	 */
	boolean next() {
		// now based on which delta is greater we can draw the line
		if (dx > dy) {
			// adjust the error term
			error += dy;

			// test if error has overflowed
			if (error >= dx) {
				error -= dx;

				// move to next line
				yy += y_inc;
			}

			// move to the next pixel
			xx += x_inc;
		} else {
			// adjust the error term
			error += dx;

			// test if error overflowed
			if (error >= dy) {
				error -= dy;

				// move to next line
				xx += x_inc;
			}

			// move to the next pixel
			yy += y_inc;
		}

		count++;
		return count < length;
	}

	/**
	 * Plot a line between (x1,y1) and (x2,y2). To step through the line use next().
	 * 
	 * @return the length of the line (which will be 1 more than you are expecting).
	 */
	int plot(int x1, int y1, int x2, int y2) {
		// compute horizontal and vertical deltas
		dx = x2 - x1;
		dy = y2 - y1;

		// test which direction the line is going in i.e. slope angle
		if (dx >= 0) {
			x_inc = 1;
		} else {
			x_inc = -1;
			dx = -dx; // need absolute value
		}

		// test y component of slope

		if (dy >= 0) {
			y_inc = 1;
		} else {
			y_inc = -1;
			dy = -dy; // need absolute value
		}

		xx = x1;
		yy = y1;

		if (dx > dy) {
			error = dx >> 1;
		} else {
			error = dy >> 1;
		}

		count = 0;
		length = Math.max(dx, dy) + 1;
		return length;
	}
}